﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class SolKMP
{
    public int[] GetPrefix(string modeStr)//这个计算的 只是前缀表
    {
        int[] next= new int[modeStr.Length];


        for(int i = 0; i < modeStr.Length; i++)
        {//遍历模式串的所有子串

            int nextVal = 0;

            for(int j = i; j >0; j--)
            {
                //字串的范围是modeStr[0:i]
                //比较子串的前后缀是否一样
                if(ComparePrefix(j, i, modeStr))//如果有最大子缀
                {
                        nextVal = j;
                    break;
                }

            }

            //Console.WriteLine(modeStr[i]);
            next[i] = nextVal;
        }
        return next;

    }

    private bool ComparePrefix(int len, int end, string modeStr)
    {
        //计算前后缀的长度
        for (int j = 0;j <len; j++)
        {
            if(modeStr[j]!= modeStr[end - len+j+1])
            {
                return false;
            }
        }
        return true;




    }

    public int[] GetNext(string modeStr)
    {
        int[] next = GetPrefix(modeStr);
        for(int i = next.Length-1; i >0;i--)
        {
            next[i] = next[i-1];
        }
        next[0] = -1;
        return next;

    } 
    
    public int[] GetNextDP(string modeStr)//动态规划求next
    {
        int[] next = new int[modeStr.Length];
        

        
            int j = 0, k = -1;
            //next[0] = -1;
        next[j] = k;
        while (j < modeStr.Length - 1)
            {
            if (k == -1 || modeStr[j] == modeStr[k])
            //k等于-1就不继续了，直接k++；  next[j] = k=0了;
            //不是-1还相同的话就直接k++；注意j先++了，所以是改变的下一个值。
            {
                j++; k++;
                next[j] = k;
            }
            else {
                k = next[k];
            }//k回到前面
            }
        return next;
    }

}

class ProgramKmp
{


    static void MainKMP(string[] args)
    {

        string MainStr = "googlzasgoogle";
        string ModeStr = "google";
        //string ModeStr = "aaaab";
        SolKMP s = new SolKMP();
        int[] res=s.GetNextDP(ModeStr);
        for(int i = 0;i < res.Length;i++)
        {
            //Console.WriteLine(res[i]);
            //Console.Write(res[i]);
            Console.WriteLine(res[i]);
        }

        

        //开始匹配
        int pos= MatchModeStr(MainStr, ModeStr);
        Console.WriteLine("子串的起始位置"+pos);
        Console.ReadKey();
    }

    private static int MatchModeStr(string mainStr, string modeStr)
    {
        
        SolKMP s = new SolKMP();
        int[] next = s.GetNextDP(modeStr);

        int i = 0;
        int j = 0;
        while(i< mainStr.Length&& j < modeStr.Length) 
        {
            if (j==-1|| modeStr[j] == mainStr[i] )
            {
                j++;
                i++;
            }
            else
            {
                j = next[j];
               
               
            }


        }
        Console.WriteLine("子串的起始位置");
        if (j== modeStr.Length)//匹配成功
        {
            return i - modeStr.Length;
        }
        else
        {
            return -1;
        }
        
        
        
        
        


    }
}
